import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class GenerateFollowSet {
    //保存需要的相关信息
    private List<Formula> formulas;
    private List<String> terminals;
    private List<String> nonTerminals;
    private Map<String, List<String>> firsts;
    private Map<String, List<String>> follows;

    public GenerateFollowSet(List<Formula> formulas,
                             List<String> terminals,
                             List<String> nonTerminals,
                             Map<String, List<String>> firsts,
                             Map<String, List<String>> follows) {
        this.formulas = formulas;
        this.terminals = terminals;
        this.nonTerminals = nonTerminals;
        this.firsts = firsts;
        this.follows = follows;
    }

    public void setFollow() {
        //初始化非终结符follow集并置空
        List<String> follow;
        for (String nonTerminal : nonTerminals) {
            follow = new ArrayList<>();
            follows.put(nonTerminal, follow);
        }
        //置#于开始符号的follow中
        follows.get(Config.initSymbol).add("#");

        System.out.println("开始生成follow集合-------------------------");
        boolean isChange = true;//只是为了进入循环这样设置
        //循环直到所有的first集合不再发生变化为止
        while (isChange) {
            isChange = false;
            //遍历产生式
            for (Formula formula : formulas) {
                String left, right, afterRight;
                String[] rights = formula.getRight();
                //从右边依此处理符号
                for (int i = 0; i < rights.length; i++) {
                    right = rights[i];
                    //如果有A -> aBCD 则把C的first加入B的follow

                    //非终结符
                    if (nonTerminals.contains(right)) {
                        //标识CD的first中是否有$
                        boolean hasNull = true;
                        //查找i+1个位置上的符号并将i+1的first放入i的follow
                        for (int j = i + 1; j < rights.length; j++) {
                            afterRight = rights[j];
                            for (String s : firsts.get(afterRight)) {
                                if (follows.get(right).contains(s) ||
                                        s.equals("$")) {
                                    continue;
                                } else {
                                    follows.get(right).add(s);
                                    isChange = true;
                                }
                            }
                            //判断i+1的first集是否含有$
                            //如果有就可以继续把i+2的first集放进来
                            //没有就说明i的follow集和i+1之后的first集合无关，退出循环
                            if (isHasNull(afterRight)) {
                                continue;
                            } else {
                                hasNull = false;
                                break;
                            }
                        }
                        //在A -> aBCD中，如果离开循环后hasNull是true，说明C和D都能推出$
                        //此时应该把A的follow给B的follow
                        if (hasNull) {
                            left = formula.getLeft();
                            Iterator<String> iterator = follows.get(left).iterator();
                            while (iterator.hasNext()) {
                                String s = iterator.next();
                                if (!follows.get(right).contains(s)) {
                                    follows.get(right).add(s);
                                    isChange = true;
                                }
                            }
                        }
                    }
                }
            }

        }

        //"#"并不代表任何实际的终结符，因此，在计算结束后，从Follow集合中移除"#"
        String left;
        for (String nonTerminal : nonTerminals) {
            left = nonTerminal;
            for (int i = 0; i < follows.get(left).size(); i++) {
                if (follows.get(left).get(i).equals("#"))
                    follows.get(left).remove(i);
            }
        }

        //语法分析中需要#
        for (String notTerminal : nonTerminals) {
            follows.get(notTerminal).add("#");
        }
    }

    private boolean isHasNull(String symbol) {
        String[] rights;
        for (Formula formula : formulas) {
            //找到产生式
            if (formula.getLeft().equals(symbol)) {
                //symbol -> rights
                rights = formula.getRight();
                if (rights[0].equals("$")) {
                    return true;
                }
            }
        }
        return false;
    }
}
